package solution;

import solution.bean.ListNode;

import java.util.HashSet;
import java.util.Set;


/*
* 141
* */
public class HasCycle {

    /*
    * 使用哈希表去重
    * */
    public boolean solution(ListNode head) {
        if (head != null && head.next != null){
            Set<ListNode> set = new HashSet<>();
            while (head != null){
                if (!set.add(head)) {
                    return true;
                }
                head = head.next;
            }
        }

        return false;
    }

    /*
    * 官方使用快慢指针
    * 快指针的步数应该可以计算最优速度
    * */
    public boolean solution2(ListNode head){
//        if (head == null || head.next == null){
//            return false;
//        }
//
//        ListNode slow = head;
//        ListNode fast = head.next;
//        while (slow != fast){
//            if (fast == null || fast.next == null){
//                return false;
//            }
//            slow = slow.next;
//            fast = fast.next.next;
//        }
//        return true;

        if (head != null && head.next != null){
            ListNode slow = head;
            ListNode fast = head.next;
            while (slow != fast){
                if (fast == null || fast.next == null){
                    return false;
                }
                slow = slow.next;
                fast = fast.next.next;
            }
            return true;
        }

        return false;
    }

    /*
    * 快慢指针写法2
    * 慢指针不用判空
    * head不用判空
    * 只对快指针判空即可
    * */
    public boolean solution3(ListNode head){
        ListNode slow = head;
        ListNode quick = head;
        while (quick != null && quick.next != null){
            quick = quick.next.next;
            slow = slow.next;
            if (quick == slow){
                return true;
            }
        }
        return false;
    }

    /*
    * 删除 + 递归
    * */
    public boolean soluetion4(ListNode head){
        if (head == null || head.next == null){
            return false;
        }

        //如果出现head.next = head表示有环
        if (head.next == head){
            return true;
        }

        //当前节点的next指向他自己，相当于把它删除了
        ListNode nextNode = head.next;
        head.next = head;

        return soluetion4(nextNode);
    }


    /*
    * 将链表翻转
    * 如果有环，那么链表反转之后，原来的头结点和反转之后的头结点一定是同一个
    * 但是操作失败
    * */
    public boolean soluetion5(ListNode head){
        //翻转链表
        ListNode rev = null;
        if (head != null){
            ListNode temp = head.next;
            head.next = rev;
            rev = head;
            head = temp;
        }

        if (head != null && head.next != null && rev == head){
            return true;
        }
        return false;
    }


}
